package leetcode_acm.backtrack;

import org.junit.Test;

import java.sql.ClientInfoStatus;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年03月23日 14:26
 */
public class RestoreIpAddresses {
    private List<String> list = new ArrayList<>();
    public static final String SEP = ".";
    public List<String> restoreIpAddresses(String s) {
        if(s == null){
            return Collections.emptyList();
        }
        char[] str = s.toCharArray();
        if(str.length == 0){
            return Collections.emptyList();
        }
        //开始递归回溯
        backtrack(str,str.length,0,0,new ArrayList<>());
        return list;
    }
    private void backtrack(char[] s, int length, int pointSum, int startIndex, List<String> path){
        if(pointSum == 3){
            if(isValid(s,startIndex,length-1)){
                String thisString = new String(s,startIndex,length-startIndex);
                //然后封装这个字符串
                StringBuilder sb = new StringBuilder();
                for (String s1 : path) {
                    sb.append(s1).append(SEP);
                }
                sb.append(thisString);
                list.add(sb.toString());
            }
            return;
        }
        //然后是单层的递归逻辑
        for(int i = startIndex;i < length;i++){
            //判断区间[startIndex,i]是否合法
            if(isValid(s,startIndex,i)){//如果是合法的,那么就将当前的区间加入到path中
                path.add(new String(s,startIndex,i-startIndex+1));
                backtrack(s, length, pointSum+1, i+1, path);
                path.remove(path.size()-1);
            }
        }
    }
    private boolean isValid(char[] s,int l,int r){
        //判断是否有前导0
        if(l > r){
            return false;
        }
        if(s[l] == '0' && l != r){
            return false;
        }
        int num = 0;
        for(int i = l;i <= r;i++){
            if(s[i] > '9' || s[i] < '0'){
                return false;
            }
            num = num*10+(s[i]-'0');
            if(num > 255){
                return false;
            }
        }
        return true;
    }

    @Test
    public void test(){
        System.out.println(restoreIpAddresses("25525511135"));
    }

}
